package com.yileiqian.util;

public class LinkedList<T> {
	private Node<T> head;
	private Node<T> end;
	private int length;

	public LinkedList() {
		length = 0;
	}

	public void insert(T value) {
		if (head == null) {
			head = new Node<T>(value);
			end = head;
		} else {
			end.setNext(new Node<T>(value));
			end = end.next();
		}

		length++;
	}

	public T get(int index) {
		if (index >= length || index < 0) {
			throw new IllegalArgumentException();
		}
		int i = 0;
		Node<T> node = head;
		while (i++ < index) {
			node = node.next();
		}
		return node.getValue();
	}

	public T getNthToLast(int index) {
		if (index < 0) {
			throw new IllegalArgumentException();
		}

		Node<T> p1 = head;
		Node<T> p2 = head;

		for (int i = 0; i < index - 1; i++) {
			if (p2 == null) {
				throw new IllegalArgumentException();
			}
			p2 = p2.next();
		}
		if (p2 == null) {
			throw new IllegalArgumentException();
		}

		while (p2.next() != null) {
			p1 = p1.next();
			p2 = p2.next();
		}

		return p1.getValue();
	}

	public void delete(int index) {
		if (index >= length || index < 0) {
			throw new IllegalArgumentException();
		}
		if (index == 0) {
			head = head.next();
		} else {
			Node<T> parent = head;
			Node<T> node = head.next();
			int i = 1;

			while (i++ < index) {
				parent = node;
				node = node.next();
			}

			if (node != null) {
				parent.setNext(node.next());
			} else {
				parent.setNext(null);
			}
		}
		length--;
	}

	/**
	 * Unsupported
	 * 
	 * @param node
	 */
	public void delete(Node<T> node) {
		if (node == null || node.next() == null) {
			throw new IllegalArgumentException();
		}

		node.setNext(node.next().next());
		node.setValue(node.next().getValue());
	}

	public int length() {
		return length;
	}

	public void pairReserve() {
		Node<T> po = null;
		Node<T> p = head;
		while (p != null && p.next() != null) {
			Node<T> next = p.next();
			Node<T> nextNext = p.next().next();
			next.setNext(p);
			p.setNext(nextNext);
			if (po != null) {
				po.setNext(next);
				po = p;
			} else {
				po = p;
				head = next;
			}
			p = nextNext;
		}
	}

	public void reserve() {
		if (head == null || head.next() == null) {
			return;
		}

		Node<T> p1 = null;
		Node<T> p2 = head;
		Node<T> p3 = null;
		while (p2 != null) {
			p3 = p2.next();
			p2.setNext(p1);
			p1 = p2;
			p2 = p3;
		}
		head = p1;
	}

	public void accessAll() {
		Node<T> node = head;
		while (node != null) {
			System.out.print(node.getValue() + " ");
			node = node.next();
		}
		System.out.println();
	}

	public static void main(String args[]) {
		LinkedList<Integer> list = new LinkedList<Integer>();
		list.insert(5);
		list.insert(2);
		list.insert(4);
		list.insert(6);
		list.insert(1);
		list.insert(3);
		list.insert(10);
		list.accessAll();
		list.reserve();
		list.accessAll();
	}
}
